{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Snakes and Ladders"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: snakesAndLadders"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #蛇梯棋"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个大小为 <code>n x n</code> 的整数矩阵 <code>board</code> ，方格按从&nbsp;<code>1</code> 到 <code>n<sup>2</sup></code> 编号，编号遵循 <a href=\"https://baike.baidu.com/item/%E7%89%9B%E8%80%95%E5%BC%8F%E8%BD%AC%E8%A1%8C%E4%B9%A6%E5%86%99%E6%B3%95/17195786\">转行交替方式</a><strong> </strong>，<strong>从左下角开始</strong>&nbsp;（即，从 <code>board[n - 1][0]</code> 开始）每一行交替方向。</p>\n",
    "\n",
    "<p>玩家从棋盘上的方格&nbsp;<code>1</code> （总是在最后一行、第一列）开始出发。</p>\n",
    "\n",
    "<p>每一回合，玩家需要从当前方格 <code>curr</code> 开始出发，按下述要求前进：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>选定目标方格 <code>next</code> ，目标方格的编号符合范围&nbsp;<code>[curr + 1, min(curr + 6, n<sup>2</sup>)]</code> 。\n",
    "\n",
    "\t<ul>\n",
    "\t\t<li>该选择模拟了掷 <strong>六面体骰子</strong> 的情景，无论棋盘大小如何，玩家最多只能有 6 个目的地。</li>\n",
    "\t</ul>\n",
    "\t</li>\n",
    "\t<li>传送玩家：如果目标方格 <code>next</code> 处存在蛇或梯子，那么玩家会传送到蛇或梯子的目的地。否则，玩家传送到目标方格 <code>next</code> 。&nbsp;</li>\n",
    "\t<li>当玩家到达编号 <code>n<sup>2</sup></code> 的方格时，游戏结束。</li>\n",
    "</ul>\n",
    "\n",
    "<p><code>r</code> 行 <code>c</code> 列的棋盘，按前述方法编号，棋盘格中可能存在 “蛇” 或 “梯子”；如果 <code>board[r][c] != -1</code>，那个蛇或梯子的目的地将会是 <code>board[r][c]</code>。编号为 <code>1</code> 和 <code>n<sup>2</sup></code> 的方格上没有蛇或梯子。</p>\n",
    "\n",
    "<p>注意，玩家在每回合的前进过程中最多只能爬过蛇或梯子一次：就算目的地是另一条蛇或梯子的起点，玩家也 <strong>不能</strong> 继续移动。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>举个例子，假设棋盘是 <code>[[-1,4],[-1,3]]</code> ，第一次移动，玩家的目标方格是 <code>2</code> 。那么这个玩家将会顺着梯子到达方格 <code>3</code> ，但 <strong>不能</strong> 顺着方格 <code>3</code> 上的梯子前往方格 <code>4</code> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回达到编号为&nbsp;<code>n<sup>2</sup></code> 的方格所需的最少移动次数，如果不可能，则返回 <code>-1</code>。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2018/09/23/snakes.png\" style=\"width: 500px; height: 394px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]\n",
    "<strong>输出：</strong>4\n",
    "<strong>解释：</strong>\n",
    "首先，从方格 1 [第 5 行，第 0 列] 开始。 \n",
    "先决定移动到方格 2 ，并必须爬过梯子移动到到方格 15 。\n",
    "然后决定移动到方格 17 [第 3 行，第 4 列]，必须爬过蛇到方格 13 。\n",
    "接着决定移动到方格 14 ，且必须通过梯子移动到方格 35 。 \n",
    "最后决定移动到方格 36 , 游戏结束。 \n",
    "可以证明需要至少 4 次移动才能到达最后一个方格，所以答案是 4 。 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>board = [[-1,-1],[-1,3]]\n",
    "<strong>输出：</strong>1\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == board.length == board[i].length</code></li>\n",
    "\t<li><code>2 &lt;= n &lt;= 20</code></li>\n",
    "\t<li><code>grid[i][j]</code> 的值是 <code>-1</code> 或在范围 <code>[1, n<sup>2</sup>]</code> 内</li>\n",
    "\t<li>编号为 <code>1</code> 和 <code>n<sup>2</sup></code> 的方格上没有蛇或梯子</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [snakes-and-ladders](https://leetcode.cn/problems/snakes-and-ladders/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [snakes-and-ladders](https://leetcode.cn/problems/snakes-and-ladders/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,-1,-1,-1,-1,-1],[-1,35,-1,-1,13,-1],[-1,-1,-1,-1,-1,-1],[-1,15,-1,-1,-1,-1]]', '[[-1,-1],[-1,3]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        total = n*n\n",
    "        def num_to_coordinates(num):\n",
    "            # determine the number should sit on which level from bottom to up\n",
    "            rem = num % n\n",
    "            if rem == 0:\n",
    "                level = num // n\n",
    "            else:\n",
    "                level = num // n + 1\n",
    "            row = n-level\n",
    "            # determine if seat of the number should left to right or the other side  \n",
    "            if level % 2 != 0:\n",
    "            # from left to right\n",
    "                col = rem - 1 if rem != 0 else n-1\n",
    "            else:\n",
    "            # from right to left\n",
    "                col = n-rem if rem != 0 else 0\n",
    "            return row, col\n",
    "            \n",
    "            \n",
    "        queue = deque()\n",
    "        queue.append((1, 0))\n",
    "        visited = set()\n",
    "        visited.add(1)\n",
    "        while queue:\n",
    "            cur, steps = queue.popleft()\n",
    "            if cur >= total:\n",
    "                return steps\n",
    "            for next_num in range(cur+1, cur+7):\n",
    "                if next_num > total:\n",
    "                    break\n",
    "                dx, dy = num_to_coordinates(next_num)\n",
    "                board_num = board[dx][dy]\n",
    "                if board_num == -1 and next_num not in visited:\n",
    "                    queue.append((next_num, steps+1))\n",
    "                    visited.add(next_num)\n",
    "                elif board_num != -1 and board_num not in visited:\n",
    "                    queue.append((board_num, steps+1))\n",
    "                    visited.add(board_num)\n",
    "        return -1\n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        m, index, nums = len(board), 1, [1]\n",
    "        for i in range(m-1, -1, -1):\n",
    "            if index % 2 == 1:\n",
    "                nums.extend(board[i])\n",
    "            else:\n",
    "                nums.extend(board[i][::-1])\n",
    "            index += 1\n",
    "        \n",
    "        m = len(nums)\n",
    "        q, steps, visited = [1], [0]*m, [False]*m\n",
    "        visited[1] = True\n",
    "        \n",
    "        while q:\n",
    "            now = q.pop(0)\n",
    "            if now == m-1: return steps[now]\n",
    "            for i in range(1, 7):\n",
    "                nxt = now + i\n",
    "                if nxt > m-1: break\n",
    "                if nums[nxt] != -1: nxt = nums[nxt]\n",
    "                if not visited[nxt]:\n",
    "                    visited[nxt] = True\n",
    "                    steps[nxt] = steps[now] + 1\n",
    "                    q.append(nxt)\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "import math\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 所有路径中的最短路径问题\n",
    "        # 使用广度优先搜索\n",
    "        # 为了减少时间复杂度，要记录已经访问过的节点\n",
    "        N = len(board)\n",
    "        queue = deque([1])\n",
    "        used = {1} # 记录已经访问过的节点\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            ans += 1\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                for dx in range(1,7):\n",
    "                    nex = cur + dx\n",
    "                    if nex <= N**2:\n",
    "                        # 计算nex在board上的坐标\n",
    "                        flag = math.ceil(nex/N)\n",
    "                        x = N - flag # 横坐标\n",
    "                        if flag&1 == 1:\n",
    "                            y = nex - N*(flag-1) - 1\n",
    "                        else:\n",
    "                            y = N*flag - nex\n",
    "                        # 若board[x][y] != -1\n",
    "                        if board[x][y] != -1:\n",
    "                            nex = board[x][y]\n",
    "                        if nex == N**2:\n",
    "                            return ans\n",
    "                        if nex not in used:\n",
    "                            queue.append(nex)\n",
    "                            used.add(nex)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        if not board or not board[0]:\n",
    "            return 0\n",
    "        \n",
    "        nrow, ncol = len(board), len(board[0])\n",
    "        jrange = list(range(ncol-1, -1, -1))\n",
    "        grid = [0]\n",
    "\n",
    "        for i in range(nrow-1, -1, -1):\n",
    "            jrange = jrange[::-1]\n",
    "            for j in jrange:\n",
    "                grid.append (board[i][j])\n",
    "        \n",
    "        L = len(grid)\n",
    "        que = [1]\n",
    "        vis = {1}\n",
    "        step= 0\n",
    "        \n",
    "        while que:\n",
    "\n",
    "            n_q = []\n",
    "            while que:\n",
    "                cur = que.pop()\n",
    "                if cur == L-1:\n",
    "                    return step\n",
    "\n",
    "                for np in range(min(cur+6, L-1), cur, -1):\n",
    "                    if grid[np] != -1:\n",
    "                        np = grid[np]\n",
    "                        \n",
    "                    if np not in vis:\n",
    "                        vis.add( np)\n",
    "                        n_q.append (np)\n",
    "# 这里不能先判断梯子起点是否已访问，也不能把梯子起点加入已访问，否则某点既是梯子终点又是起点时会出问题\n",
    "# case [[-1,-1,-1,46,47,-1,-1,-1],[51,-1,-1,63,-1,31,21,-1],[-1,-1,26,-1,-1,38,-1,-1],[-1,-1,11,-1,14,23,56,57],[11,-1,-1,-1,49,36,-1,48],[-1,-1,-1,33,56,-1,57,21],[-1,-1,-1,-1,-1,-1,2,-1],[-1,-1,-1,8,3,-1,6,56]]\n",
    "#                     if np in vis:\n",
    "#                         continue\n",
    "                        \n",
    "#                     vis.add( np)\n",
    "#                     if grid[np] == -1:\n",
    "#                         n_q.append (np)\n",
    "#                     else:\n",
    "#                         if grid[np] not in vis:\n",
    "#                             n_q.append (grid[np])\n",
    "#                             vis.add (grid[np])\n",
    "                    \n",
    "            step +=1\n",
    "            que  = n_q\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        vis = [0] * (n * n)\n",
    "        stk = [(0, 0)]\n",
    "        vis[0] = 1\n",
    "        def step_to(s):\n",
    "            ni = s // n\n",
    "            nj = s % n\n",
    "            j = n - 1 - nj if ni & 1 else nj\n",
    "            i = n - 1 - ni\n",
    "            return s if board[i][j] == -1 else board[i][j] - 1\n",
    "\n",
    "        while stk:\n",
    "            s, step = stk.pop()\n",
    "            if s == n * n - 1: return step\n",
    "            for p in range(1, 7):\n",
    "                if s + p >= n * n: break\n",
    "                to = step_to(s + p)\n",
    "                if not vis[to]:\n",
    "                    vis[to] = 1\n",
    "                    stk.insert(0, (to, step+1))\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        # find snakes and ladders\n",
    "        n = len(board)\n",
    "        i = 1\n",
    "        r, c = n - 1, 0\n",
    "        sl = {}\n",
    "        while i <= n * n:\n",
    "            if board[r][c] != -1:\n",
    "                sl[i] = board[r][c]\n",
    "            \n",
    "            if (n - r) % 2:\n",
    "                if c < n - 1:\n",
    "                    c += 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            else:\n",
    "                if c > 0:\n",
    "                    c -= 1\n",
    "                else:\n",
    "                    r -= 1\n",
    "            i += 1\n",
    "        \n",
    "        queue = [1]\n",
    "        visited = {1}\n",
    "        step = 1\n",
    "        while queue:\n",
    "            lenq = len(queue)\n",
    "            for _ in range(lenq):\n",
    "                now = queue.pop(0)\n",
    "                for i in range(1, 7):\n",
    "                    if now + i == n * n or sl.get(now + i, 0) == n * n:\n",
    "                        return step\n",
    "                    if now + i > n * n:\n",
    "                        break\n",
    "                        \n",
    "                    if now + i not in sl and now + i not in visited:\n",
    "                        queue.append(now + i)\n",
    "                        visited.add(now + i)\n",
    "                    elif now + i in sl and sl[now+i] not in visited:\n",
    "                        queue.append(sl[now+i])\n",
    "                        visited.add(sl[now+i])\n",
    "            step += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        k = 1\n",
    "        seen = {1}\n",
    "        q = [(1, 0)]\n",
    "        while q:\n",
    "            p, s = q.pop(0)\n",
    "            if p == n * n:\n",
    "                return s\n",
    "            for i in range(1, 7):\n",
    "                if p + i <= n * n:\n",
    "                    t = p + i - 1\n",
    "                    r = n - 1 - t // n\n",
    "                    c = t % n if r % 2 != n % 2 else n - 1 - t % n\n",
    "                    if board[r][c] != -1:\n",
    "                        t = board[r][c] - 1\n",
    "                        r = n - 1 - t // n\n",
    "                        c = t % n if r % 2 != n % 2 else n - 1 - t % n\n",
    "                    if t + 1 not in seen:\n",
    "                        seen.add(t + 1)\n",
    "                        q.append((t + 1, s + 1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        path = [0]\n",
    "        N = len(board)\n",
    "        for i in range(N):\n",
    "            if i % 2 == 0:\n",
    "                path += board[N-1-i]\n",
    "            else:\n",
    "                path += board[N-1-i][::-1]\n",
    "        n = len(path) - 1\n",
    "        visited = [0 for i in range(n+1)]\n",
    "        queue = [(1,0)]\n",
    "        visited[1] = 1\n",
    "        T = []\n",
    "        while queue:\n",
    "            node, step = queue[0]\n",
    "            queue.pop(0)\n",
    "            for i in range(1,7):\n",
    "                if node + i > n: break\n",
    "                next = node + i if path[node + i] == -1 else path[node + i]\n",
    "                if next == n: T.append(step+1)\n",
    "                if visited[next] == 0:\n",
    "                    queue.append((next, step+1))\n",
    "                    visited[next] = 1\n",
    "        if T:\n",
    "            return min(T)\n",
    "        else:\n",
    "            return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        from collections import deque\n",
    "        N = len(board)\n",
    "        nums = [-1]\n",
    "        for i in range(N):\n",
    "            if i % 2 == 0:\n",
    "                nums += board[N - 1 - i]\n",
    "            else:\n",
    "                for j in range(N - 1, -1, -1):\n",
    "                    nums.append(board[N - 1 - i][j])\n",
    "        min_step = [400] * (N * N + 1)\n",
    "        min_step[1] = 0\n",
    "        stack = deque()\n",
    "        stack.append([1, 0])\n",
    "        while stack:\n",
    "            cur, step = stack.popleft()\n",
    "            if cur == N * N:\n",
    "                return step\n",
    "            for i in range(6, 0, -1):\n",
    "                if cur + i <= N * N:\n",
    "                    if nums[cur + i] != -1 and step + 1 < min_step[nums[cur + i]]:\n",
    "                        min_step[nums[cur + i]] = step + 1\n",
    "                        stack.append([nums[cur + i], step + 1])\n",
    "                    elif nums[cur + i] == -1 and step + 1 < min_step[cur + i]:\n",
    "                        min_step[cur + i] = step + 1\n",
    "                        stack.append([cur + i, step + 1])\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        N = len(board)\n",
    "        if N <= 2:\n",
    "            return 1\n",
    "        def square2xy(square: int) -> (int, int):\n",
    "            square -= 1\n",
    "            x = square // N\n",
    "            y = square % N if x % 2 == 0 else N - 1 - square % N\n",
    "            return (N - 1 - x, y)\n",
    "        finf = float(\"inf\")\n",
    "        res = [finf] * (N * N + 1)\n",
    "        res[N * N] = 0\n",
    "        for i in range(2, 8):\n",
    "            res[-i] = 1\n",
    "        changed = True\n",
    "        while changed:\n",
    "            changed = False\n",
    "            for i in range(N * N - 7, 0, -1):\n",
    "                mins = finf\n",
    "                for j in range(1, 7):\n",
    "                    index = i + j\n",
    "                    x, y = square2xy(index)\n",
    "                    if board[x][y] != -1:\n",
    "                        index = board[x][y]\n",
    "                        #print(index)\n",
    "                    mins = min(mins, res[index] + 1)\n",
    "                if res[i] != mins:\n",
    "                    changed = True\n",
    "                res[i] = mins\n",
    "            #print(res)\n",
    "        return res[1] if res[1] < finf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def get_num(self, board, index, num):\n",
    "        div = (index - 1) // num\n",
    "        mod = (index - 1) % num\n",
    "        # div是奇数\n",
    "        rol = num - div -1\n",
    "        if div % 2 == 0:\n",
    "            column = mod\n",
    "        else:\n",
    "            column = num - 1 - mod\n",
    "        return board[rol][column]\n",
    "    \n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        all_list = [1]\n",
    "        result = {1: 0}\n",
    "        num = len(board)\n",
    "        max_num = num * num\n",
    "        while all_list:\n",
    "            index = all_list[0]\n",
    "            del all_list[0]\n",
    "            if index == max_num:\n",
    "                return result[index]\n",
    "            for item in range(index + 1, min(index+6, max_num) +1):\n",
    "\n",
    "                value = self.get_num(board, item, num)\n",
    "                if value == -1:\n",
    "                    after_index = item\n",
    "                else:\n",
    "                    after_index = value\n",
    "                if result.get(after_index) is None:\n",
    "                    result[after_index] = result[index] + 1\n",
    "                    all_list.append(after_index)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 坐标转换  \n",
    "class Solution(object):\n",
    "    def snakesAndLadders(self, board):\n",
    "        N = len(board)\n",
    "\n",
    "        def get(s):\n",
    "            # Given a square num s, return board coordinates (r, c)\n",
    "            quot, rem = divmod(s-1, N)\n",
    "            row = N - 1 - quot\n",
    "            col = rem if row%2 != N%2 else N - 1 - rem\n",
    "            return row, col\n",
    "\n",
    "        dist = {1: 0}\n",
    "        queue = collections.deque([1])\n",
    "        while queue:\n",
    "            s = queue.popleft()\n",
    "            if s == N*N: return dist[s]\n",
    "            for s2 in range(s+1, min(s+6, N*N) + 1):\n",
    "                r, c = get(s2)\n",
    "                if board[r][c] != -1:\n",
    "                    s2 = board[r][c]\n",
    "                if s2 not in dist:\n",
    "                    dist[s2] = dist[s] + 1\n",
    "                    queue.append(s2)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        step_num = 0\n",
    "        climb_nodes = set()\n",
    "\n",
    "        tran_board = [0, ]\n",
    "        board_length = len(board)\n",
    "        for line_index in range(board_length):\n",
    "            for column_index in range(board_length):\n",
    "                if line_index % 2 == 0:\n",
    "                    tran_board.append(board[board_length-line_index-1][column_index])\n",
    "                else:\n",
    "                    tran_board.append(board[board_length-line_index-1][board_length-column_index-1])\n",
    "\n",
    "        step_nodes = [1, ]\n",
    "        while len(step_nodes):\n",
    "            step_num += 1\n",
    "\n",
    "            next_step_nodes = []\n",
    "            for node in step_nodes:\n",
    "                for go_step in range(1, 7):\n",
    "                    next_node = node + go_step\n",
    "                    if tran_board[next_node] != -1:\n",
    "                        next_node = tran_board[next_node]\n",
    "                    if next_node == board_length**2:\n",
    "                        return step_num\n",
    "                    if next_node not in climb_nodes:\n",
    "                        climb_nodes.add(next_node)\n",
    "                        next_step_nodes.append(next_node)\n",
    "            step_nodes = next_step_nodes\n",
    "\n",
    "        return -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        pq = [[0, 1]]\n",
    "        seen = set()\n",
    "        while pq:\n",
    "            curStep, curPos = heapq.heappop(pq)\n",
    "            if curPos == n * n:\n",
    "                return curStep\n",
    "            for nxtPos1 in range(curPos + 1, curPos + 7):\n",
    "                if 0 <= nxtPos1 <= n * n and (curPos, nxtPos1) not in seen:\n",
    "                    nxtx = n - (nxtPos1 - 1) // n - 1\n",
    "                    if n & 1:\n",
    "                        nxty = n - (nxtPos1 - 1) % n - 1 if nxtx & 1 else (nxtPos1 - 1) % n\n",
    "                    else:\n",
    "                        nxty = (nxtPos1 - 1) % n if nxtx & 1 else n - (nxtPos1 - 1) % n - 1\n",
    "                    if board[nxtx][nxty] != -1:\n",
    "                        nxtPos2 = board[nxtx][nxty]\n",
    "                        if (curPos, nxtPos2) not in seen:\n",
    "                            heapq.heappush(pq, [curStep + 1, nxtPos2])\n",
    "                            seen.add((curPos, nxtPos2))\n",
    "                    else:\n",
    "                        heapq.heappush(pq, [curStep + 1, nxtPos1])\n",
    "                        seen.add((curPos, nxtPos1))\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        sum_cell = len(board)**2\n",
    "        if sum_cell == 4:\n",
    "            return 1\n",
    "        \n",
    "        self.board = board\n",
    "        dp = [0]*sum_cell # steps from 0 to j\n",
    "        i=0\n",
    "        while i<sum_cell:\n",
    "            if dp[i] == 0 and i !=0:\n",
    "                i+=1\n",
    "                continue\n",
    "            for k in range(1,7):\n",
    "                t = self.getBoardValue(i+k)\n",
    "                # if i ==28:\n",
    "                #     print(\"--\",k,t)\n",
    "                m = t-1 if t!=-1 else i+k\n",
    "                if 0<m<sum_cell:\n",
    "                    if dp[m]>0:\n",
    "                        \n",
    "                        if t!=-1 and t-1<i+k and dp[i]+1<dp[t-1]:\n",
    "                            dp[m] = min(dp[m], dp[i]+1)\n",
    "                            i=m-1\n",
    "                            break\n",
    "                        else:\n",
    "                            dp[m] = min(dp[m], dp[i]+1)\n",
    "                    else:\n",
    "                        dp[m] = dp[i] + 1\n",
    "                        \n",
    "            i+=1\n",
    "        for i in range(len(dp)):\n",
    "            print(i,dp[i])\n",
    "        return -1 if dp[sum_cell-1]==0 else dp[sum_cell-1]\n",
    "        \n",
    "    \n",
    "    def getBoardValue(self,n):\n",
    "        l = len(self.board)\n",
    "        r = l - n // l - 1\n",
    "        c = -1\n",
    "        if (l-r)%2 == 1:\n",
    "            c = n%l\n",
    "        else:\n",
    "            c = l - n%l - 1\n",
    "        \n",
    "        return self.board[r][c]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "import math\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board):\n",
    "        \"\"\"\n",
    "        :type board: List[List[int]]\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        # 所有路径中的最短路径问题\n",
    "        # 使用广度优先搜索\n",
    "        N = len(board)\n",
    "        queue = deque([1])\n",
    "        used = set()\n",
    "        ans = 0\n",
    "        while queue:\n",
    "            length = len(queue)\n",
    "            ans += 1\n",
    "            for _ in range(length):\n",
    "                cur = queue.popleft()\n",
    "                used.add(cur)\n",
    "                for dx in range(1,7):\n",
    "                    nex = cur + dx\n",
    "                    if nex <= N**2:\n",
    "                        # 计算nex在board上的坐标\n",
    "                        flag = math.ceil(nex/N)\n",
    "                        x = N - flag # 横坐标\n",
    "                        if flag&1 == 1:\n",
    "                            y = nex - N*(flag-1) - 1\n",
    "                        else:\n",
    "                            y = N*flag - nex\n",
    "                        # 若board[x][y] != -1\n",
    "                        if board[x][y] != -1:\n",
    "                            nex = board[x][y]\n",
    "                        if nex == N**2:\n",
    "                            return ans\n",
    "                        if nex not in used:\n",
    "                            queue.append(nex)\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    # BFS\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        def move(pos, step):\n",
    "            pos += step\n",
    "            r = n - (pos - 1) // n - 1\n",
    "            c = (pos - 1) % n\n",
    "            if n % 2 == r % 2:\n",
    "                c = n - c - 1\n",
    "            if board[r][c] == -1:\n",
    "                return pos\n",
    "            else:\n",
    "                return board[r][c]\n",
    "\n",
    "        queue, V = [1], {1}\n",
    "        ans, n = 0, len(board)\n",
    "        target = n * n\n",
    "\n",
    "        while queue:\n",
    "            new_queue = []\n",
    "            ans += 1\n",
    "            for cur in queue:\n",
    "                for step in range(1, 6 + 1):\n",
    "                    pos = move(cur, step)\n",
    "                    if pos == target:\n",
    "                        return ans\n",
    "                    if pos not in V:\n",
    "                        V.add(pos)\n",
    "                        new_queue.append(pos)\n",
    "            queue = new_queue\n",
    "\n",
    "        return -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        q = {1}\n",
    "        visited = {1}\n",
    "        res = 0\n",
    "        while q:\n",
    "            tmp = set()\n",
    "            for val in q:\n",
    "                if val == n * n:\n",
    "                    return res\n",
    "                for i in range(val + 1, min(val + 7, n * n + 1)):\n",
    "                    r, c = n - 1 - (i - 1) // n, (i - 1) % n if (i - 1) % (2 * n) < n else n - 1 - (i - 1) % n\n",
    "                    tar = board[r][c] if board[r][c] != -1 else i\n",
    "                    if tar not in visited:\n",
    "                        tmp.add(tar)\n",
    "                        visited.add(tar)\n",
    "            q = tmp\n",
    "            res += 1\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "\n",
    "        def id2rc(idx: int) -> (int, int):\n",
    "            r, c = (idx - 1) // n, (idx - 1) % n\n",
    "            if r % 2 == 1:\n",
    "                c = n - 1 - c\n",
    "            return n - 1 - r, c\n",
    "        vis = set()\n",
    "        q = deque([(1, 0)])\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            for i in range(1, 6 + 1):\n",
    "                idx_nxt = idx + i\n",
    "                if idx_nxt > n * n:  \n",
    "                    break\n",
    "                x_nxt, y_nxt = id2rc(idx_nxt)  \n",
    "                if board[x_nxt][y_nxt] > 0: \n",
    "                    idx_nxt = board[x_nxt][y_nxt]\n",
    "                if idx_nxt == n * n: \n",
    "                    return step + 1\n",
    "                if idx_nxt not in vis:\n",
    "                    vis.add(idx_nxt)\n",
    "                    q.append((idx_nxt, step + 1)) \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        def trans_pos(num):\n",
    "            num = num - 1\n",
    "            x = n - (num // n) - 1\n",
    "            rx = num // n\n",
    "            y = num % n\n",
    "            if rx % 2:\n",
    "                y = n - y - 1\n",
    "            return x, y\n",
    "        \n",
    "        n = len(board)\n",
    "        q = deque([1])\n",
    "        step = 0\n",
    "        seen = {1}\n",
    "        while q:\n",
    "            m = len(q)\n",
    "            for _ in range(m):\n",
    "                cur = q.popleft()\n",
    "                if cur == n * n:\n",
    "                    return step\n",
    "                for nxt in range(cur + 1, min(cur + 6, n * n) + 1):\n",
    "                    if nxt in seen:\n",
    "                        continue\n",
    "                    seen.add(nxt)\n",
    "                    x, y = trans_pos(nxt)\n",
    "                    if board[x][y] == -1:\n",
    "                        q.append(nxt)\n",
    "                    else:\n",
    "                        q.append(board[x][y])\n",
    "            step += 1\n",
    "        return -1\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        def idx2rc(idx, n):\n",
    "            row_b = (idx + n - 1) // n\n",
    "            row_t = n - row_b\n",
    "            if row_b % 2 == 1:\n",
    "                col = (idx - 1) % n\n",
    "                return row_t, col\n",
    "            else:\n",
    "                col = (idx - 1) % n\n",
    "                return row_t, n - 1 - col\n",
    "\n",
    "        n = len(board)\n",
    "        ans = float('inf')\n",
    "        q = deque()\n",
    "        q.append((0, 1))\n",
    "        vis = [[False] * n for _ in range(n)]\n",
    "        vis[n-1][0] = True\n",
    "\n",
    "        while q:\n",
    "            cost, idx = q.popleft()\n",
    "            if idx == n ** 2: ans = min(ans, cost)\n",
    "            for idx_other in range(idx + 1, min(idx + 6, n ** 2)+1):\n",
    "                x, y = idx2rc(idx_other, n)\n",
    "                if board[x][y] == -1:\n",
    "                    if not vis[x][y]: \n",
    "                        q.append((cost + 1, idx_other))\n",
    "                        vis[x][y] = True\n",
    "                else:\n",
    "                    other = board[x][y]\n",
    "                    nr, nc = idx2rc(other, n)\n",
    "                    if not vis[nr][nc]:\n",
    "                        q.append((cost + 1, other))\n",
    "                        vis[nr][nc] = True\n",
    "        print(vis)\n",
    "        return ans if ans != float('inf') else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def getxy(label, n):\n",
    "    r = (label - 1) % n;\n",
    "    i = (label - 1) // n;\n",
    "    if i & 1:\n",
    "        return n - 1 - (label - 1) // n, n - 1 -r\n",
    "    else:\n",
    "        return n - 1 - (label - 1) // n, r\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "        m = n * n\n",
    "        q = [[0, 0] for _ in range(m * 6 -5)]\n",
    "\n",
    "        q[0][1] = 1\n",
    "        tail = 0\n",
    "        head = 1\n",
    "        visited = [0] * (m + 1)\n",
    "\n",
    "        while tail <= head:\n",
    "            print(head)\n",
    "            step, label = q[tail]\n",
    "            tail += 1\n",
    "\n",
    "            if visited[label]:\n",
    "                continue\n",
    "            visited[label] = 1\n",
    "            if label == m:\n",
    "                return step            \n",
    "            for ne in range(label + 1, min(label + 6, m ) + 1):\n",
    "                x, y = getxy(ne, n)\n",
    "                if ne not in (1, m) and board[x][y] != -1:\n",
    "                    ne = board[x][y]\n",
    "                if visited[ne]:\n",
    "                    continue\n",
    "                #q.append([step + 1, ne])\n",
    "\n",
    "                q[head][0] = step + 1\n",
    "                q[head][1] = ne\n",
    "                head += 1\n",
    "\n",
    "        \n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        skip=[0]\n",
    "        for i,line in enumerate(board[::-1]):\n",
    "            if i%2==0:\n",
    "                skip.extend(line)\n",
    "            else:\n",
    "                skip.extend(line[::-1])\n",
    "        # print(skip)\n",
    "        visit=[False]*len(skip)\n",
    "        target=len(skip)-1\n",
    "        ans=0\n",
    "        queue=[1,]\n",
    "        while queue:\n",
    "            queue2=[]\n",
    "            for a in queue:\n",
    "                if visit[a]:continue\n",
    "                visit[a]=True\n",
    "                if skip[a]!=-1:    #跳\n",
    "                    a=skip[a]\n",
    "                if a==target:return ans\n",
    "                for b in range(a+1,1+min(a+6,target)):\n",
    "                    queue2.append(b)\n",
    "            ans+=1\n",
    "            queue=queue2\n",
    "        return -1\n",
    "\n",
    "\n",
    "\n",
    "            \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "\n",
    "        def id2rc(idx: int) -> (int, int):\n",
    "            r, c = (idx - 1) // n, (idx - 1) % n\n",
    "            if r % 2 == 1:\n",
    "                c = n - 1 - c\n",
    "            return n - 1 - r, c\n",
    "        \n",
    "        visit = set()\n",
    "        q = [(1, 0)]\n",
    "        while q:\n",
    "            idx, step = q.pop(0)\n",
    "            for i in range(1, 6 + 1):\n",
    "                idx_nxt = idx + i\n",
    "                if idx_nxt > n * n:   # 超出边界\n",
    "                    break\n",
    "                \n",
    "                x_nxt, y_nxt = id2rc(idx_nxt)   # 得到下一步的行列\n",
    "                if board[x_nxt][y_nxt] > 0:   # 存在蛇或梯子\n",
    "                    idx_nxt = board[x_nxt][y_nxt]\n",
    "                if idx_nxt == n * n:   # 到达终点\n",
    "                    return step + 1\n",
    "                if idx_nxt not in visit:\n",
    "                    visit.add(idx_nxt)\n",
    "                    q.append((idx_nxt, step + 1))   # 扩展新状态\n",
    "        \n",
    "        return -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def snakesAndLadders(self, board: List[List[int]]) -> int:\n",
    "        n = len(board)\n",
    "\n",
    "        def id2rc(idx: int) -> (int, int):\n",
    "            r, c = (idx - 1) // n, (idx - 1) % n\n",
    "            if r % 2 == 1:\n",
    "                c = n - 1 - c\n",
    "            return n - 1 - r, c\n",
    "        \n",
    "        vis = set()\n",
    "        q = deque([(1, 0)])\n",
    "        while q:\n",
    "            idx, step = q.popleft()\n",
    "            for i in range(1, 6 + 1):\n",
    "                idx_nxt = idx + i\n",
    "                if idx_nxt > n * n:   # 超出边界\n",
    "                    break\n",
    "                \n",
    "                x_nxt, y_nxt = id2rc(idx_nxt)   # 得到下一步的行列\n",
    "                if board[x_nxt][y_nxt] > 0:   # 存在蛇或梯子\n",
    "                    idx_nxt = board[x_nxt][y_nxt]\n",
    "                if idx_nxt == n * n:   # 到达终点\n",
    "                    return step + 1\n",
    "                if idx_nxt not in vis:\n",
    "                    vis.add(idx_nxt)\n",
    "                    q.append((idx_nxt, step + 1))   # 扩展新状态\n",
    "        \n",
    "        return -1\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
